今天的部分就輕鬆很多，這裡就只介紹線性搜尋和二元搜尋。

線性搜尋

線性搜尋(linear search):把想搜尋的目標跟array中的值一個一個對比。時間複雜度: O(N), 空間複雜度: O(1)。

def LinearSearch(array,target):
    for i in range(len(array)):
        if array[i]==target:
            return f'the index is {i}'
    return 'Cannot find the target'

mylist=[5,90,1,32]

print(LinearSearch(mylist,90))
>> the index is 1

二元搜尋

二元搜尋(Binary Search):二元搜尋法為較線性搜尋法快的一個做法，每次可以少搜尋一半的數值，但二元搜尋僅適用於經排列後的陣列(sorted array)。其每次都與中間值做比較，若小於中間值，將末端設為中間值前面的值，再取中間值再比較，以此類推。若大於中間值，則將起始值設為中間值後面一個的值，再取中間值，再比較，以此類推。其時間複雜度為: O(logN)，空間複雜度: O(1)。直接看程式碼可能比較好理解:

import math
def BinarySearch(array,target):
    start=0
    end=len(array)-1
    mid=math.floor((start+end)/2)
    while not (array[mid]==target or start>=end):
        if target<array[mid]:
            end=mid-1
        else:
            start=mid+1
        mid=math.floor((start+end)/2)
    if array[mid]==target:
        return mid
    else:
        return 'The value is not found!'
 
mylist=[1,5,10,25,30,35,40]

print(BinarySearch(mylist,30))
>> 4

參考資料:
本文為The Complete Data Structures and Algorithms Course in Python (from Udemy)的筆記，有興趣可以自己上去看看~